package com.yangzhe.algorithm.c040;

// N皇后问题
// 测试链接 : https://leetcode.cn/problems/n-queens-ii/
public class NQueens {

    /**
     * 思路1：递归，用数组记录皇后位置
     * 一、变量
     * 1. 数组path：length = 0。举例（不是答案） ：[1, 3, 4, 5] 代表是4皇后问题，共4行，1行1列，2行3列，3行4列，4行5列放了航后
     * 2. 变量i：代表当前递归的行，i < n
     *
     * <p>
     * 二、基础判断
     * 1. 同行不能放皇后，由于递归设计是按行递归，每行只放一个，所以这个问题不用判断
     * 2. 同列不能放皇后，列号不相等即可：path[i] != path[i-x]
     * 3. 对角不能放皇后， |当前行 - 之前行| != |当前列 - 之前列|
     * <p>
     * 三、递归方法设计 nQueens = f(i, path, n)
     * 1. 遍历当前行每个位置
     * 2. 如果该位置可以放皇后，则设置path[i] = 列，调用子递归f(i + 1, path, n)
     * 3. 如果该位置不能放皇后，则啥也不做
     * 4. base case：如果i == n，代表已经到底了，证明之前每行都放了皇后，代表是一种解，返回1
     *
     * @param n n皇后
     * @return
     */
    public static int totalNQueens1(int n) {
        int[] path = new int[n];

        return f(0, path, n);
    }

    public static int f(int i, int[] path, int n) {
        // base case
        if (i == n) {
            return 1;
        }

        int nQueens = 0;
        // 遍历当前行的每一列
        for (int c = 1; c <= n; c++) {
            if (canPlaceQueen(i, c, path)) {
                path[i] = c;
                nQueens += f(i + 1, path, n);
            }
        }

        return nQueens;
    }

    /**
     * 判断是否可以放皇后
     *
     * @param i    当前行
     * @param c    当前列
     * @param path 之前放皇后的位置
     * @return
     */
    public static boolean canPlaceQueen(int i, int c, int[] path) {
        // 遍历之前的每一行
        for (int i1 = 0; i1 < i; i1++) {
            // 1. 判断同列
            if (c == path[i1]) {
                return false;
            }

            // 2. 判断对角线
            if (Math.abs(i - i1) == Math.abs(c - path[i1])) {
                return false;
            }
        }

        return true;
    }

    /**
     * 思路2：用数字的位记录皇后位置
     * 一、变量设计
     * 1. limit： 为1的位代表可以放皇后的位，(1 << n + 1) -1，例如4皇后问题，则limit = (1 << 5) - 1 = 00010000 - 1 = 00001111
     * 1. col：二进制位，1代表当前行的这一列不能放皇后，之前行已经放过了，例如 1101，代表只有第2列能放皇后
     * 2. leftCol：二进制位，1代表当前行的这一列不能放皇后，之前的【左】上方已经放过了 leftCol = (leftCol | 当前列) >> 1
     * 3. rightCol：进制位，1代表当前行的这一列不能放皇后，之前的【右】上方已经放过了 rightCol = (rightCol | 当前列) << 1
     * <p>
     * 二、基础判断
     * 1. 行不用判断，见思路1
     * 2. 不能放皇后的位置ban = col | leftCol | rightCol
     * <p>
     * 三、递归流程  nQueens = f(col, leftCol, rightCol, limit)
     * 1. base case: col == limit，代表之前的每一列都放了皇后，则是一种解，返回1
     * 2. 可以放置皇后的位置：candidate = limit & ~(ban)
     * 3. 遍历每一个place = candidate & (-candidate)
     * 4. col = place | col，leftCol = (leftCol | place) >> 1，rightCol = (rightCol | place) << 1
     * 5. 去掉候选位置 candidate = candidate ^ place
     * 6. 调用子递归f(col, leftCol, rightCol, limit)
     *
     * @param n
     * @return
     */
    public static int totalNQueens2(int n) {
        int limit = (1 << n) - 1;
        int col = 0;
        int leftCol = 0;
        int rightCol = 0;

        return f(col, leftCol, rightCol, limit);
    }

    public static int f(int col, int leftCol, int rightCol, int limit) {
        // base case: 代表之前每一列都放了皇后，是一种解
        if (col == limit) {
            return 1;
        }

        // 遍历每一列，判断是否可以放皇后
        int nQueens = 0;
        // 不能放皇后的位置为 1
        int ban = col | leftCol | rightCol;
        // 可以放皇后的位置为1
        int candidate = limit & (~ban);

        while (candidate != 0) {
            // 取最右侧的1 相当于 candidate & (~candidate + 1)
            int place = candidate & (-candidate);

            // 消除最右侧的1，相当于已经放置过了
            candidate ^= place;

            nQueens += f(col | place, (leftCol | place) >> 1, (rightCol | place) << 1, limit);
        }
        return nQueens;
    }

    public static void main(String[] args) {
        int n = 16;
        long start, end;
        System.out.println("测试开始");
        System.out.println("解决" + n + "皇后问题");
        start = System.currentTimeMillis();
        System.out.println("方法1答案 : " + totalNQueens1(n));
        end = System.currentTimeMillis();
        System.out.println("方法1运行时间 : " + (end - start) + " 毫秒");

        start = System.currentTimeMillis();
        System.out.println("方法2答案 : " + totalNQueens2(n));
        end = System.currentTimeMillis();
        System.out.println("方法2运行时间 : " + (end - start) + " 毫秒");
        System.out.println("测试结束");

//        System.out.println("=======");
//        System.out.println("只有位运算的版本，才能10秒内跑完16皇后问题的求解过程");
//        start = System.currentTimeMillis();
//        int ans = totalNQueens2(16);
//        end = System.currentTimeMillis();
//        System.out.println("16皇后问题的答案 : " + ans);
//        System.out.println("运行时间 : " + (end - start) + " 毫秒");
    }

}
